|
Combinatorial game theory (CGT) is a branch of applied mathematics and theoretical computer science that typically studies sequential games with perfect information. Study is largely confined to two-player games which have a ''position'' in which the players take turns changing in defined ways or ''moves'' to achieve a defined winning condition. CGT has not traditionally studied games randomness and imperfect or incomplete information (sometimes called games of chance, like poker), favoring games whose position is public to both players, and in which the set of available moves is also public (perfect information).〔Lessons in Play, p. 3〕 Combinatorial games include well-known games like chess, checkers, Go, Arimaa, Hex, and Connect6. They also include one-player combinatorial puzzles, and even no-player automata, like Conway's Game of Life.〔http://erikdemaine.org/papers/AlgGameTheory_GONC3/paper.pdf〕 In CGT, the moves in these games are represented as a game tree. Game theory in general includes games of chance, games of imperfect knowledge, and games in which players can move simultaneously, and they tend to represent real-life decision making situations. CGT has a different emphasis than "traditional" or "economic" game theory, which was initially developed to study games with simple combinatorial structure, but with elements of chance (although it also considers sequential moves, see extensive-form game). Essentially, CGT has contributed new methods for analyzing game trees, for example using surreal numbers, which are a subclass of all two-player perfect-information games.〔 The type of games studied by CGT is also of interest in artificial intelligence, particularly for automated planning and scheduling. In CGT there has been less emphasis on refining practical search algorithms (like the alpha-beta pruning heuristic included in most artificial intelligence textbooks today), but more emphasis on descriptive theoretical results (like measures of game complexity or proofs of optimal solution existence without necessarily specifying an algorithm – see strategy-stealing argument for instance). An important notion in CGT is that of solved game (which has several flavors), meaning for example that one can prove that the game of tic-tac-toe results in a draw if both players play optimally. While this is a trivial result, deriving similar results for games with rich combinatorial structures is difficult. For instance, in 2007 it was announced that checkers has been (weakly, but not strongly) solved—optimal play by both sides also leads to a draw—but this result was a computer-assisted proof. Other real world games are mostly too complicated to allow complete analysis today (although the theory has had some recent successes in analyzing Go endgames). Applying CGT to a ''position'' attempts to determine the optimum sequence of moves for both players until the game ends, and by doing so discover the optimum move in any position. In practice, this process is tortuously difficult unless the game is very simple. ==History== CGT arose in relation to the theory of impartial games, in which any play available to one player must be available to the other as well. One very important such game is nim, which can be solved completely. Nim is an impartial game for two players, and subject to the ''normal play condition'', which means that a player who cannot move loses. In the 1930s, the Sprague-Grundy theorem showed that all impartial games are equivalent to heaps in nim, thus showing that major unifications are possible in games considered at a combinatorial level (in which detailed strategies matter, not just pay-offs). In the 1960s, Elwyn R. Berlekamp, John H. Conway and Richard K. Guy jointly introduced the theory of a partisan game, in which the requirement that a play available to one player be available to both is relaxed. Their results were published in their book ''Winning Ways for your Mathematical Plays'' in 1982. However, the first book published on the subject was Conway's ''On Numbers and Games'', also known as ONAG, which introduced the concept of surreal numbers and the generalization to games. ''On Numbers and Games'' was also a fruit of the collaboration between Berlekamp, Conway, and Guy. Combinatorial games are generally, by convention, put into a form where one player wins when the other has no moves remaining. It is easy to convert any finite game with only two possible results into an equivalent one where this convention applies. One of the most important concepts in the theory of combinatorial games is that of the sum of two games, which is a game where each player may choose to move either in one game or the other at any point in the game, and a player wins when his opponent has no move in either game. This way of combining games leads to a rich and powerful mathematical structure. John Conway states in ONAG that the inspiration for the theory of partisan games was based on his observation of the play in go endgames, which can often be decomposed into sums of simpler endgames isolated from each other in different parts of the board. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Combinatorial game theory」の詳細全文を読む スポンサード リンク
|